#include "snake_move.h"
#include <queue>

extern vector<Snake_cell> snake;

int foodx, foody;

typedef struct info {
	int x, y, dis;

	info(int _x, int _y, int _dis) :x(_x), y(_y), dis(_dis) {}
}Info;

extern char map[15][15];

int snakeMove(int dx, int dy) {
	int head_x = snake[0].x, head_y = snake[0].y, len = snake.size();
	int tail_x = snake[len - 1].x, tail_y = snake[len - 1].y;
	int tar_x = head_x + dx, tar_y = head_y + dy, game = 1;

	for (int i = len - 1; i >= 1 ; i--) {
		snake[i] = snake[i - 1];
		map[snake[i].x][snake[i].y] = SNAKE_BODY;
	}

	map[tail_x][tail_y] = BLANK_CELL;

	if (map[tar_x][tar_y] == SNAKE_BODY || map[tar_x][tar_y] == WALL_CELL) {
		game = 0;
		map[tail_x][tail_y] = BLANK_CELL;
	}
	else {
		snake[0].x = tar_x;
		snake[0].y = tar_y;

		if (map[tar_x][tar_y] == SNAKE_FOOD) {
			snake.push_back(Snake_cell(tail_x, tail_y));
			map[tail_x][tail_y] = SNAKE_BODY;
			put_money();
		}
		else {
			map[tail_x][tail_y] = BLANK_CELL;
		}

	}
	map[tar_x][tar_y] = SNAKE_HEAD;

	output_map();

	return game;
}

int calculate_distance(int x, int y) {
	bool has_exp[15][15] = { 0 };
	int dis[15][15] = { 0 };
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
	dis[x][y] = 0;

	queue<Info> que;

	que.push(Info(x, y, 0));
	has_exp[x][y] = true;

	while (!que.empty()) {
		Info temp = que.front();
		que.pop();

		//printf("tempx = %d, tempy = %d\n", temp.x, temp.y);

		for (int i = 0; i < 4; i++) {
			//printf("i = %d\n", i);
			if (has_exp[temp.x + dx[i]][temp.y + dy[i]] == false && (map[temp.x + dx[i]][temp.y + dy[i]] == BLANK_CELL || map[temp.x + dx[i]][temp.y + dy[i]] == SNAKE_FOOD)) {
				que.push(Info(temp.x + dx[i], temp.y + dy[i], temp.dis + 1));
				has_exp[temp.x + dx[i]][temp.y + dy[i]] = true;
				if (map[temp.x + dx[i]][temp.y + dy[i]] == SNAKE_FOOD) {
					return temp.dis + 1;
				}
			}
		}
		
	}

	return 9999;
	
}

char how_to_move() {
	int head_x = snake[0].x, head_y = snake[0].y, len = snake.size();
	int min_dis = 9999;

	//printf("foodx = %d, foody = %d\n", foodx, foody);
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 }, minn = 0;
	char op[4] = {'w', 'a', 's', 'd'};

	for (int i = 0; i < 4; i++) {
		if (map[head_x + dx[i]][head_y + dy[i]] == BLANK_CELL) {
			int dis = calculate_distance(head_x + dx[i], head_y + dy[i]);
			//int dis = abs(head_x + dx[i] - foodx) + abs(head_y + dy[i] - foody);
			//printf("i = %d, dis = %d\n", i, dis);

			if (dis < min_dis) {
				min_dis = dis;
				minn = i;
			}
		}
		else if (map[head_x + dx[i]][head_y + dy[i]] == SNAKE_FOOD) {
			return op[i];
		}
	}

	if (min_dis == 9999) {
		for (int i = 0; i < 4; i++) {
			if (map[head_x + dx[i]][head_y + dy[i]] == BLANK_CELL) {
				return op[i];
			}
		}
	}
	//printf("minn = %d\n", minn);

	//system("pause");

	return op[minn];
}